//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 
//
// 整数除法仅保留整数部分。 
//
// 你可以假设给定的表达式总是有效的。所有中间结果将在 [-2³¹, 2³¹ - 1] 的范围内。 
//
// 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "3+2*2"
//输出：7
// 
//
// 示例 2： 
//
// 
//输入：s = " 3/2 "
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：s = " 3+5 / 2 "
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 3 * 10⁵ 
// s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开 
// s 表示一个 有效表达式 
// 表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内 
// 题目数据保证答案是一个 32-bit 整数 
// 
//
// Related Topics 栈 数学 字符串 👍 747 👎 0


package com.tyrone.leetcode.editor.cn;

import javax.xml.parsers.SAXParser;
import java.util.Stack;

public class BasicCalculatorIi {
    public static void main(String[] args) {
        Solution solution = new BasicCalculatorIi().new Solution();
        int calculate = solution.calculate("0-2147483647");
        System.out.println(calculate);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 2 * 2 + 2 * 3
         * 2 + 2 * 2 + 3
         * 2 + 2 * 3 / 3
         * 2 * 3 + 2
         *
         * @param s
         * @return
         */
        public int calculate(String s) {
            String trim = s.replaceAll(" ", "");
            Stack<String> stack = new Stack<>();
            Stack<String> tmp = new Stack<>();
            char[] arr = trim.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                String curr = String.valueOf(arr[i]);
                if (curr.equals(" "))
                    continue;
                if (isNumber(curr)) {
                    StringBuilder builder = new StringBuilder();
                    builder.append(curr);
                    int j = i + 1;
                    while (j < arr.length && isNumber(arr[j])) {

                        builder.append(arr[j]);
                        j++;
                    }
                    stack.push(builder.toString());
                    i = j - 1;
                } else if (isSmallerSymbol(curr)) {
                    stack.push(curr);
                } else {
                    String last = stack.pop();
                    StringBuilder builder = new StringBuilder();
                    int j = i + 1;
                    while (j < arr.length && isNumber(arr[j])) {

                        builder.append(arr[j]);
                        j++;
                    }
                    String next = builder.toString();
                    i = j;
                    stack.push(calculate(last, next, curr));
                    i = j - 1;
                }
            }
            int result = 0;
            while (!stack.isEmpty()) {
                tmp.push(stack.pop());
            }
            String pop = tmp.pop();
            result  = Integer.valueOf(pop);
            while (!tmp.isEmpty()){
                String sym = tmp.pop();
                String pop2 = tmp.pop();
                result = Integer.valueOf(calculate(String.valueOf(result),pop2,sym));
            }
            return result;
        }

        boolean isNumber(char ch) {
            return ch - '0' >= 0 && ch - '0' <= 9;
        }

        boolean isNumber(String ch) {
            return !(ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/"));
        }

        boolean isSmallerSymbol(String ch) {
            return ch.equals("+") || ch.equals("-");
        }

        String calculate(String ch1, String ch2, String symbol) {
            if (symbol.equals("+")) {
                return String.valueOf(Integer.valueOf(ch1) + Integer.valueOf(ch2));
            } else if (symbol.equals("-")) {
                return String.valueOf(Integer.valueOf(ch1) - Integer.valueOf(ch2));
            } else if (symbol.equals("*")) {
                return String.valueOf(Integer.valueOf(ch1) * Integer.valueOf(ch2));
            } else {
                return String.valueOf(Integer.valueOf(ch1) / Integer.valueOf(ch2));
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}